In a single first-in/first-out (FIFO) structure, only one input port is used to accept transactions. Because it does not have the capability of providing sufficient data throughput, the FIFO structure presents a drawback in a multi-threaded environment in which transactions may happen concurrently.
A multi-in and multi-out FIFO structure provides the capability to accept transactions concurrently. The multi-in and multi-out FIFO comprises multiple parallel single-in and single-out FIFOs with the same or different number of entries. No matter how many input ports are, the structures of all the single-in and single-out FIFOs composing the FIFO structure are usually uniform. In other words, it is easy to expand to any number of ports. However, because this FIFO structure has multiple output ports, it loses the property of first-in and first-out and must have additional mechanism to maintain the order of transactions.
As an example, one device uses a pipelining architecture to perform read transactions. Before the prior read transaction completes, the subsequent request is issued. Because multiple input ports are provided by the multi-in and multi-out FIFO, it is possible that the prior request is queued into one port and the subsequent request is queued into another port. If the output control of the two ports is independent, the later request may pass through the prior one and the response order of the two read transactions will be reversed.
The same problem of reversed order also occurs in a multi-in and multi-out posted FIFO. Once the write transaction is posted into the posted FIFO, the device producing the write data presumes that the write transaction it issued has been completed and may want to issue another transaction for setting a flag to inform the consumer to take the data away. If the write transaction setting the flag is outputted from the FIFO earlier than the one carrying data, the data consumer will read the flag first and then may read the wrong data before the correct data actually reach the destination.
To avoid mixing up the order between posted and non-posted FIFO in a system, the following method may be adopted. The non-posted FIFO will reject non-posted transactions temporarily until all of the prior posted write transactions are actually retired in the consuming end of the posted FIFO. At the same time, the posted FIFO must block the subsequent posted write transactions that will disturb the read transaction. Although this method is simple and intuitive, it breaks the concurrency of read and write transactions and is not practicable in a multi-threaded system.